
% CHAPTER 4
\chapter{PROPOSED METHODS FOR TRAFIC AWARE ROUTING IN IEEE 802.16J NON-TRANSPARENT NETWORKS}
\label{chp:workdone}
IEEE 802.16j Multihop Relaying extends the network coverage and increases the network throughput. One of the usage areas of 802.16j is the rural areas where shadow affect is more likely to occur because of geographic conditions. Considering a tactical area network in rural area, dense of the network traffic is communication between the subscribers in the same area. In such cases routing data over MR-BS for the communicating pair in the same region is a waste of resources. Moreover, since all the communication paths are established between MSs and MR-BS, relay links at higher levels become bottleneck. For data traffic between subscribers with common RS, forwarding packets directly to downlink connection of the destination is an effective solution. Path selection method is also an important factor for increasing network throughput.
 
In IEEE 802.16j maximum resource utilization is gained in non-transparent mode with distributed scheduling. Consider the IEEE 802.16j non-transparent network topology given in Figure \ref{fig:chapter4_1}. Imagine that there are communications between MS1-MS2 and MS2-MS3. At the same time, all the subscribers downloading data from the internet. In this scenario without shortcut routing, communication path of MS1-MS2 is MS1-\textgreater{}RS2-\textgreater{}RS1-\textgreater{}MR-BS1-\textgreater{}RS1-\textgreater{}RS2-\textgreater{}MS2. Enabling the shortcut routing RS2 would forward the data destined to MS2 directly to MS2 instead of forwarding to RS1. In this case path will be MS1-\textgreater{}RS2-\textgreater{}MS2. By this way hop count decreases from six to two. Moreover, uplink resources of RS1 and MR-BS1 will not be wasted.
\input{chapter4/figure1}
In Figure \ref{fig:chapter4_1}, if the MS4 initiates network traffic destined to MS1, data will be sent over backbone network. Since MS1 is also in the coverage of RS3, it may be more appropriate to select RS3 as an access station of MS1. This decision should be made by path selection algorithm. Taking traffic demand into consideration while selecting the access station may prevent unnecessary traversals.   
\section{Shortcut Routing}
Routing is a responsibility of Network Layer in IP based networks. In IEEE 802.16j MR Networks, Relay Stations are composed of Data Link and Physical layers. Therefore IP based routing is not available in RSs. RSs forward the incoming data directly to one of the downlink or uplink link according to CID. For traffic between two subscribers having common superordinate RS, forwarding data directly to destination subscriber from RS may increase network utilization. By keeping destination IP address, transport CID pair in a routing cache, RS can forward data packet by inspecting the destination IP address. Since IP address is IP layer information and CID is MAC layer information, to keep both information together we need a cross layer on top of the MAC layer. 

In this section integration of cross layer on top of MAC layer of IEEE 802.16j NT RS will be mentioned. 
\subsection{Assumptions}
Assumption for shortcut routing are listed below:
\begin{itemize}
	\item Only one transport connection is established for each MS.
	\item All service flows are type of UGS.
	\item RSs run on non-transparent mode with distributed scheduling.
\end{itemize}
\subsection{Cross Layer for Shortcut Routing}
Transport connections are created upon service flow creation request initiated either by MR-BS or MS. Service flow creation procedure is started with DSA-REQ message. Service flows must be associated with a transport connection. This connection may be an existing one or it can be created upon request. MR-BS decides the path for transport connection and informs all the intermediate RSs about path. RSs keep CID and link pairs in MAC layer routing table. When a data is received, RS checks CID of the MAC packet and forwards it to corresponding link. Example path creation scenario is shown in Figure \ref{fig:chapter4_2}.
\input{chapter4/figure2}
In Figure \ref{fig:chapter4_2} MS is the originator of DSA-REQ message. This message is sent to MR-BS on management connection. After MR-BS determines the path for transport connection, it sends DSA-REQ or DSC-REQ message to RSs which are the intermediate stations on the path. RSs checks available resources whether it can satisfy the service demands. If the intermediate station accepts the service request, they forward the message to the next RS on the path until it reaches to Access RS. If one the intermediate station rejects, the message will not reach to Access RS and connection will not be created. Upon Access RS receives the DSA-REQ message, it accepts the service request if it has available resources. MR-BS informs intermediate RS about path created with DSA/DSC-ACK message. MR-BS sends DSA-RSP message to MS to inform about acceptance of service request.

RSs keep CID and path information in MAC layer. When a data packet is received from uplink transport connection, according to its CID RS forwards the packet to next hop. For shortcut routing, target station's IP address is the key value for making direct forwarding decision. CROSS layer is inserted on protocol stack of RS as in Figure \ref{fig:chapter4_3} to handle IP based routing operations. 
\input{chapter4/figure3}
Cross Layer keeps CID and IP pairs in routing cache for IP based routing. Routing cache is dictionary structure where the key is the IP address and value is CID. Since dictionary structure does not let inserting an item with existing key, only one connection could be associated with given IP address. Routing cache is constructed and updated upon connection creations. As depicted in Figure \ref{fig:chapter4_2}, after Access RS accepts service acquisition request, MR-BS informs intermediate RSs on the path with DSA-ACK which includes path and CID information in TLV encoded message section. Upon intermediate RSs received this message, CID and IP address of the MS will be sent to CROSS to update routing cache. For disconnection or handover scenarios of MS, MR-BS sends MS\_INFO-DEL message to Access Station to delete MS related information and to release resources allocate to it. This message is sent on management connection over intermediate RSs. Intermediate RSs would inspect this message to update routing cache.
\input{chapter4/figure4}
Figure \ref{fig:chapter4_4} shows how shortcut routing decision is taken in Cross Layer. Shortcut routing mechanism works only for uplink data, so data received from superordinate station is forwarded as normal. When a MAC data packet is received from subordinate station, it is sent to cross layer instead of finding the destination link from the MAC layer routing table instead of forwarding with routing table kept in MAC. For uplink packets cross layer first extracts the data packet from the MAC packet. If packet is IP packet then routing cache is checked whether there is a record for destination IP address. If a record is found then a new MAC packet constructed with CID obtained from cache and pushed into downlink queue of destination connection. In cross layer, if there is no record found for destination address, no action is taken and MAC packet is sent back to MAC layer as in original form. MAC layer forwards packet to its superordinate station.
\section{Hierarchical Addressing and Routing for IEEE 802.16j Multihop Relay Networks}
Determining the destination of incoming data packet requires checking routing cache at cross layer. Handovers and access station changes require reconstructing routing cache. Using hierarchical addressing scheme, it can be easier to understand whether destination node is subordinate station or not.  By this way when a packet is received it is first checked destination IP is in the address block of current station. If it is, then destination CID can be obtained from routing cache. Reliability of routing cache can be improved with hierarchical addressing. 

For traffic aware routing, shortcut routing was the first step. Main factor that determines the routing path in IEEE 802.16j Networks is path selection method. Location information of destination node is necessary to make path selection according to traffic demand. By using hierarchical addressing, location of nodes can be determined inspecting the destination IP address of a packet.

In IEEE 802.16j MR Network every intermediate and leaf stations have one access station which forms tree topology. Position of a node can be easily observed in tree topology when hierarchical addressing used. Address assignment is done in a systematic manner so that each subordinate station connected to same access station will obtain addresses in same CIDR address block. 

IP address assignment is handled by MR-BS during RS and MS network entry process in IEEE 802.16j Standard. There is not any regulation for IP address assignment in the standard. With hierarchical address assignment, every superordinate station (RSs and BSs) will be considered as subnetwork. IP address block will be assigned for each subnetwork. Since both RS and BS are superordinate stations, BS would become a subnetwork of subnetworks. The same situation is also valid for RSs which have subordinate RSs. For superordinate stations which have subordinate RSs, IP address block assignment should also contain address block for subordinate RSs. Example tree topology and IP address assignment with CIDR notation is shown in Figure \ref{fig:chapter4_5}.
\input{chapter4/figure5}
In topology in Figure \ref{fig:chapter4_5} CIDR block of BS is 24 which means $2^{(32-24)} - 1$ nodes can addressed with this address block. Since RSs are also superordinate station, they are assigned an address block in network entry process. Address block assignment is done in a systematic manner. If subnet mask of address block is less than 29, address block is divided to four parts. Three parts are reserved for subordinate RSs and remaining part is used for MSs directly connected to station. In the example topology, BS assigns MS1's IP address from the first part of address block which is 17.2.1.0/26. BS's IP address is the first IP of first part of the IP address block which is 17.0.1.1. Second and third parts of the address block are assigned to RS1 and RS2 respectively. 

Systematic assignment of address block limits breadth and depth of the topology. Breadth limitation comes with dividing the each subnet block into four parts which means a superordinate station can have at most three subordinate RS. CIDR of the assigned address block of BS limits the depth of the topology. Since address block assigned to RS should have at least a.b.c.d/30 CIDR block, depth of the topology will be (32-CIDR of BS)/2. 

Main motivation behind using hierarchical addressing is to gather information about the incoming and outgoing traffic of a station. Examine MS2 in Figure \ref{fig:chapter4_1} is in the coverage of both RS1 and RS2. BS selected RS1 as an access station of MS2 by using a path selection method. If MS2 and MS3 communicates with each other, since MS2 is in the range of RS2, MS2 can understand that the incoming traffic if source IP 17.0.1.130 is pass through RS2. Eventually this gives clue about selecting RS2 as an access station of MS2 may increase throughput and decrease latency and congestion.

\section{Enhanced Mobile IP for Shortcut Routing Enabled IEEE 802.16j Networks}
Mobility comes with challenges in mobile networks. Seamless handover and addressing mobile nodes are keys issues for uninterrupted communication. IEEE 802.16 provides solution for handover and describes the procedure in details. For IP based networks, addressing of mobile nodes are handled with Mobile IP protocol which is also applicable in WiMAX. 

As stated in the background section, mobile nodes have two address which are "home address" and "care-of address". Foreign and home agents run on MR-BSs in traditional WiMAX networks. When a packet received at RS, if the destination address was one of the subordinate of RS, RS forwards the packet directly to destination MS. If MS performs handover operation then the packets forwarded from the RS will be lost. To prevent this situation, every RS should have home and foreign agent. When a subordinate station initiates handover or path change process, the requests pass through the intermediate stations. These request packets are processed at intermediate RSs to update MobileIP tables, and then forwarded to MR-BS. This solution prevents packet losses caused by migrated nodes. Also when subscriber initiates registration process with new BS, requests and responses pass through intermediate station, so all intermediate station will know about address of new comer.
\input{chapter4/figure6}
Subordinates may change access station because of mobility or to get better service from another superordinate station. These two access station change scenarios are valid for both RS and MS. For RSs the access station change task more complicated since they might have subordinate stations. When a RS with subordinate stations, changes the access station, all subordinates connected to RS should renew the IP address. Renewing the subordinate stations' IP address is the responsibility of the superordinate RS. In Figure \ref{fig:chapter4_6} RS1 changes its access station from BS1 to BS2. While connecting to BS1 MobileIP procedure works and BS2 send request to BS1 for assigning new care of address for RS1. BS1 responds and BS2 with accepting registration of RS1 and assigns its new care of address. For the completeness of hierarchy in IP address, RS2 and its subordinates should have changed IP address. RS1 assigns new addresses to its first level subordinates. Each RS is responsible for assigning IP address to its first level subordinate. In this case RS1 assigns IP address of RS2 and RS assigns IP addresses of MS1 and MS2. Since IP address assignment method proposed limits depth and breadth of topology, some nodes may be disconnected. Disconnected MSs should connect to another superordinate station in vicinity if available. Path selection method used would prevent from disconnected nodes after access station change. 
\input{chapter4/figure7}
Figure \ref{fig:chapter4_7} and Figure \ref{fig:chapter4_8} illustrates the how agents work in proposed solution. MS2 leaves the network where BS1 is the gateway station to backbone network and moves the network of BS2. Every node has home address which taken from the first network joined. In figures care of addresses of station are written. Before leaving the BS1's network, MS2 initiates handover request with candidate neighbor station. If the handover request accepted by BS1, MS2 initiates registration request to BS2. Upon receiving registration request of MS2, BS2 inserts MS2 into visitors' list record and requests BS1 to join MS2 its network with MS2's new care of address. If BS1 accepts BS2's request, it keeps the mobility information of MS2 and respond back to BS2. Each intermediate RSs which receives MS2 handover request and its response, will know about MS leaving the network. If home agent address of MS2 is declared as IP address of RS3, then MobileIP request will be destined to RS3. So RS1 and BS1 indirectly learn about the care of address of MS2. Each intermediate RS receiving MS2 registration request and its response will know about MS2's IP address and keep its care of address.   
\input{chapter4/figure8}
In the scenario examined in Figure \ref{fig:chapter4_7} and Figure \ref{fig:chapter4_8}, if MS2 has ongoing communication with many nodes, communication should not be corrupted because of handover. For outgoing traffic there wouldn't be any problem since source address of packets generated from MS2 has the home address. For incoming data, there are two conditions: 1) a node transferring data with shortcut routing, 2) a node transferring data over MR-BS. For the first case, since MS2 sends handover request to BS1 before leaving the network, all the intermediate stations along the path learn about handover. Between handover request and registration to BS2, shortcut routing is valid for MS2. Since during registration BS2 sends request to RS3 about MobileIP assignment of MS2, RS3 and its superordinates learn the care of address of MS2. Every RS and BS updates the mobility binding list when request from BS2 is received. After RS3 accepts the request of BS2, MS2 will be registered. After this point when a packet destined to MS2's home address, if the sender is outside the network of BS1 then packet will be routed to care of address of  MS2 from BS1. If the source of packet is inside the BS1's network, this means source node and MS2 had at least one common superordinate station. Shortcut routing should forward the packet to previous access station of MS2 upon receiving such a packet. However since there is a mobility record for MS2, receiving RS directly forward the incoming packet to its access station as if in traditional IEEE 802.16j network. At the end BS1 sends packet to MS2 from backbone network.
\section{Traffic Aware Path Selection for Shortcut Routing Enabled IEEE 802.16j Multihop Relay Networks}
Path selection has an important role for utilizing network resources efficiently. Path selection is the process of selecting routing path of network data. There are various metrics used in path selection. According to QoS requirements, path selection metrics and methodologies may change. For shortcut routing enabled IEEE 802.16j Networks, traffic demand is important for path selection to find the shorter routes. Without knowing the traffic destinations, it is hard to find a metric for selecting appropriate access station. In the proposed solution, traffic demand is predicted according to statistics of previous data transmission. Received and sent data statistics are used as path selection metrics in the proposed method. 

Without shortcut routing, all MS traffic would pass through MR-BS. In such cases, path selection aims to find the best routing path between MS and MR-BS. There are various metrics proposed for this problem which increases throughput and decreases congestion and latency. These metrics would be used in shortcut routing enabled networks since traffic destined to outside the network will follow routing path to MR-BS. Our focus in this study is topologies where the main data traffic is between the subscribers in limited region like tactical area. 
\subsection{Path Selection Metrics}
Metrics used for path selection is aimed to utilize the network resources efficiently. Shortcut routing avoids unnecessary packet traversals for the traffic inside network. So the problem is finding the optimum path which does not degrade the end to end throughput of MS and BS, at the same time increase the chance of shortcut routing.
\textbf{Modulation and Coding Scheme (MCS)}

WiMAX supports adaptive modulation and coding which means according to link quality, modulation and coding technique used can be changed dynamically. MSC is chosen according to SNR of a link. If channel is noisy then choosing modulation technique with lower bitrate and coding scheme with higher redundancy is more appropriate. There are seven MCS levels used in metric as in [13].  Table 6 shows SNR and MCS levels.
 
Given a bandwidth selecting MCS level as high as possible increases the throughput. If the dedicated bandwidth to user is 100 MHz and selected MCS is BPSK 1/2 then data rate will be 100 * 1/2 = 50 Kbps. Whereas if QAM64 3/4 is chosen, than it will be 100 * 6 * 3/4 = 450 Kbps. If the path consists of more than one link, link with the smallest MCS level will become a bottleneck. So when selecting the path, all link quality should be taken in consideration.
\input{chapter4/figure9}
For the shortcut routing case, even if the selected path between MS and BS have poor quality links, communication between MSs with common a RS may not affected. Consider SNR values of links in the topology given in Figure \ref{fig:chapter4_9}.  MS1 and MS2 are connected to access stations with high quality link and QAM64 3/4 is selected as MCS. Link between RS1 and RS2 has QAM64 1/2 as MCS. Bottleneck link in this topology is the link between RS1 and MR-BS which is the most necessary link for traffic outside the network. MCS level for bottleneck link is BPSK 1/2. Since traffic of communication between MS1 and MS2 does not use the link between RS1 and MR-BS, minimum MCS for routing path is QAM64 1/2. 

\textbf{Hop Count}

Hop count metric is the number of links between MR-BS and MS. Hop count affects the latency and load of intermediate RSs. For traffic scenarios which use shortcut routing, hop count between MS and MR-BS is not meaningful.

\textbf{Load}

Load of the intermediate RSs gives clue about congestion and resource availability. In uplink direction there is bandwidth reservation so there is no problem for subscriber. However in downlink direction there is no bandwidth reservation, so heavily loaded RSs become congested. To avoid congestions and packet drops; selecting RS with less congested is preferable.

\textbf{Received and Sent Traffic Statistic}

Previous three metric are used for selecting best path between MS and BS. By using these metric it is not possible to handle shortcut routing scenarios. In some cases subscribers may connect to an access station which has more hop count to MR-BS, heavily loaded superordinate stations and a relay link with poor quality. Even if in this case total network throughput may be optimal. Communicating with neighbor MSs rather than with nodes outside the network may indicate such scenarios. 
\subsection{Integration with IEEE 802.16j Standard}
In IEEE 802.16j networks, MR-BS is responsible for selecting the access station of RSs. Standard describes the access station selection for RS during network entry phase. For MSs, changing access station is considered as handover. Therefore even if MS does not change its MR-BS, handover process is applied for access station change. Either MR-BS or MS itself can take decision of handover. Consequently, proposed path selection method will run in MSs and MR-BSs.

Metrics that are used for path selection should be collected from network. In literature available management messages are used for this purpose. As in [13], we use UCD messages to gather the metrics from network for MS. MR-BS obtain neighbor information from RS\_NBR\_MEAS-REP sent by RSs. Our proposed metrics also will be carried in these messages. There are two different path selection scenarios which are path selection in network entry and path selection in operational mode. In first scenario MS/RS determines the access station and initiates ranging process. In second scenario, MR-BS or MS initiates handover process. For RS, MR-BS requests RS to change its access station. 

\textbf{RS and MS path selection during network entry}

MS starts scanning air interface during network entry phase to obtain neighbor stations channel descriptor. MS path selection procedure is shown in Figure \ref{fig:chapter4_10}. MS interprets the information obtained from UCD messages with channel measurements to calculate the metrics. MS waits for second UCD message received from same MR-BS to finish scanning. This duration is enough for receiving all UCDs sent from neighbor stations. MS starts selecting its access station to connect with the metrics obtained in scanning phase. MS starts ranging process with selected RS as described in the standard. Registration of MS to MR-BS may affect the metrics for intermediate RSs. MR-BS may change the access stations of intermediate RS during path creation phase as described in previous sections.

Same procedure is valid for RS for path selection during network entry phase.
\input{chapter4/figure10}
\textbf{MS access station change in operational state}

Due to the mobility or service requirements, MS may change its access station while in operational state. MR-BS has knowledge about network with the information obtained from backbone network and RSs. MS or MR-BS may initiate handover process for providing better service for MS. Path selection method is used to take the handover decision. Example path selection of operational MS is shown in Figure \ref{fig:chapter4_11}. MS requests scanning interval from MR-BS with MOB\_SCN-REQ. If MR-BS accepts the requests, MS starts scanning air interface in the interval specified by MR-BS. After obtained information from UCD messages received from neighbor stations, MS starts path selection procedure and selects its candidate access station. MS sends MOB\_MSHO-REQ to initiate handover with candidate access station. If MR-BS accepts, MS starts registration procedure as described in previous chapters. After MS disconnects from the previous access station, MR-BS informs the RS with MS\_INFO-DEL message.
\input{chapter4/figure11}
\textbf{RS access station change in operational state }

RSs periodically collect neighbor information to send report to MR-BS. MR-BS determines access station of RSs in operational state. Figure \ref{fig:chapter4_12} depicts access station change for RS3. RS2 is the initial access station of RS3. Due the change in the metrics, MR-BS selects RS2 as a new access station of RS3. MR-BS informs RS3 about new access station with RS-AccessRS\_REQ message. Upon receiving AccessRS\_REQ message RS3 sends generic ACK to MR-BS and starts network entry procedure by sending RNG-REQ message to RS1. The rest of the procedure works as defined in the standard.
\input{chapter4/figure12} 
\subsection{Path Selection Method}
Each RSs and MSs keep statistics about source of incoming traffic and destination of outgoing traffic. Statistics are kept in a dictionary where key is a neighbor superordinate station and data is amount of data transferred. For send and receive cases two dictionaries kept. When a data is sent to a node, it is checked whether destination IP address is inside one of the address block of superordinate stations. Similarly when a data packet received from access station, source address of IP packets is checked whether it is subordinate of the neighbor stations. 
\input{chapter4/figure13} 
Figure \ref{fig:chapter4_13} explains the usage scenario of sent \& received data metric. In topology MSs are connected to RSs and communicating with each other. MS7 enters the region which is intersection of RS2's and RS4's transmit range.  Since MS7 is new in the region, there should not be and traffic statistics in dictionary for superordinate station in the range. MS7 creates dictionary entries for new neighbor RSs and selects of them as an access station according the previous three metrics. According to previous three metrics hop count and MCS metrics are same for the path RS2 and RS4. Load of RS4 is more than RS2 because number of subordinates connected. MS7 selects RS2 as an access station at the beginning. After a while MS7's major traffic become between the MS5, MS4 and MS6. When traffic load prevails the other metrics then MS7 selects RS4 as an access station to benefit from shortcut routing. 

Each subordinate station calculates alternative path cost periodically. Alternative paths may end up with same MR-BS or not. If rating of one of the alternate paths prevails current and the alternate path ends up with different MR-BS the subordinate station starts handover process. If subordinate station is RS, then station migrates to new subnetwork with all its subordinates. If the prevailing path is also ends up with the current BS then RS sends SBC-REQ to BS with rates of the candidate stations. Extra information will be carried with TLV encoded part of the management packets. 
After selecting a new path for a subordinate, statistical data analysis may change in favor of the previous path. This could be happen repetitively if the rates of paths are nearly same. To prevent this situation, to change the path, candidate path must be better than current path rate plus threshold. 

Metrics defined in this section was grouped into two. First group of metrics are for selecting the best path to deliver packets between MS and MR-BS. The second group of metrics is for selecting path which generates more shortcut routing scenarios. Second group is meaningful where the subscribers registered to same MR-BS are communicating with each other. If density of the traffic is inside the network then second group of metrics becomes more important. As a result the path rate function, every metric has a coefficient. These coefficients may change according to the usage scenarios. Every metric value is scaled to floating point number between zero and one to equalize the weight of each metric. Path cost formula is given in Equation 2.
	
\begin{center} $P_{r-BS}= c_{MCS}.MCS_{ms-BS}+c_{H}.H_{ms-BS}+c_{L}.L_{r}+c_{S}.S_{r}+c_{R}.R_{r}  (2)$\end{center}
	
where $c_{MCS}$ coefficient is for MCS metric, $MCS_{ms-BS}$ is minimum MCS level on the path between MS and MR-BS. $H_{ms-BS}$ is hop count between MS and MR-BS and $c_{H}$ is the coefficient of the metric. $L_{r}$ is the load of the candidate access relay r.  $S_{r}$ and $R_{r}$ are sent and received data statistics to and from Relay r.
%\begin{figure}[hbt]
%\begin{center}

\textbf{Declerations}

\begin{tabular}{l l p{7cm}}
$B_{max}$ &:&Maximum avaliable UL Bandwitdh for an RS or MR-BS.\\
$MCS_{max}$ &:&Maximum assignable MCS level for a link.  \\
$CIDR_{max}$ &:&Maximum assigned CIDR block in the network (MR-BS's CIDR block). \\
$c_{MCS}$ &:&Coeffient for MCS metric. \\
$c_{hop}$ &:&Coeffient for hop count metric. \\
$c_{load}$ &:&Coeffient for load metric. \\
$c_{sent}$ &:&Coeffient for sent traffic metric. \\
$c_{recv}$ &:&Coeffient for received traffic metric. \\
$N$ &:&Neighbor RS and MR-BS stations.\\
$t$ &:&Path rate treshold multiplier. \\
\end{tabular}
\newline
\newline
\begin{algorithm}
\caption{$path\_select(N)$}
\begin{algorithmic}
	\STATE $ max\_rate \leftarrow rate\_station(curr\_access)$
	\STATE $candidate\_access \leftarrow curr\_access$
	\FORALL{ $S \in N$}
		\IF {$rate\_station(S) > max\_rate \times tres$}
			\STATE $max\_rate \leftarrow rate\_station(S)$
			\STATE $candidate\_access \leftarrow S$
		\ENDIF
	\ENDFOR
	\IF {$candidate\_access \neq curr\_access$}
		\STATE $connect\_to(candidate\_access)$
	\ENDIF
\end{algorithmic}
\end{algorithm}
\newline
\newline
\begin{algorithm}[!htp]
\caption{$rate\_station (S)$}
\begin{algorithmic}
	\STATE $aval\_bw\_ratio \leftarrow S.aval\_bw / B_{max}$
	\STATE $load\_ratio \leftarrow 1 / Log_{100} S.Congestion$
	\STATE $mcs\_ratio \leftarrow MCS(S) / MCS_{max}$
	\STATE $hop\_ratio \leftarrow (32 - S.IpAddressBlock.Subnet) / CIDR_{max}$
	\STATE $sent\_ratio \leftarrow SentAnalysis[S] / SentAnalysis.Total$
	\STATE $recv\_ratio \leftarrow RecvAnalysis[S] / RecvAnalysis.Total$
	\STATE $rate \leftarrow c_{MCS} \times mcs\_ratio + c_{hop} \times hop\_ratio + c_{sent} \times sent\_ratio + c_{recv} \times recv\_ratio + c_{load} \times load\_ratio$
	\STATE \textbf{return} $rate$
\end{algorithmic}
\end{algorithm}
%\end{center}
%\caption{Proposed path selection algorithm}
%\label{fig:chapter4_14}
%\end{figure}

Algorithm of path selection method is given in Algorithm 1. This algorithm runs of each MS and MR-BS periodically. Complexity of the algorithm is $O(n)$ for MS where n is the number of neighbor stations. For MR-BS complexity of algorithm is $O(n^2)$ since for every subordinate station, MR-BS runs path selection algorithm.
\newline
\newline\newline
\newline\newline
\newline\newline
